﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0027_LevelOrder : IAlgorithm
    {
        // 二叉树的层序遍历

        // 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

        // 示例：
        //  二叉树：[3,9,20,null,null,15,7],
        //       3
        //      / \
        //     9  20
        //       /  \
        //      15   7
        //  返回其层序遍历结果：
        //    [
        //      [3],
        //      [9,20],
        //      [15,7]
        //    ]


        public void Test()
        {
            // 算法参数定义
            var tree = new TreeNode(2)
            {
                left = new TreeNode(1)
                {
                    left = new TreeNode(3),
                    right = new TreeNode(4)
                },
                right = new TreeNode(1)
                {
                    left = new TreeNode(4),
                    right = new TreeNode(3)
                }
            };
            // 算法执行与打印
            Console.WriteLine(LevelOrder(tree));
        }

        // 算法
        // 队列，每层先全部进队，再遍历出队，记录一组
        public IList<IList<int>> LevelOrder(TreeNode root)
        {
            //边界条件判断
            if (root == null)
                return new List<IList<int>>();
            //队列
            Queue<TreeNode> queue = new Queue<TreeNode>();
            List<IList<int>> res = new List<IList<int>>();
            //根节点入队
            queue.Enqueue(root);
            //如果队列不为空就继续循环
            while (queue.Count != 0)
            {
                //BFS打印，levelNum表示的是每层的结点数
                int levelNum = queue.Count;
                //subList存储的是每层的结点值
                List<int> subList = new List<int>();
                for (int i = 0; i < levelNum; i++)
                {
                    //出队
                    TreeNode node = queue.Dequeue();
                    subList.Add(node.val);
                    //左右子节点如果不为空就加入到队列中
                    if (node.left != null)
                        queue.Enqueue(node.left);
                    if (node.right != null)
                        queue.Enqueue(node.right);
                }
                //把每层的结点值存储在res中，
                res.Add(subList);
            }
            return res;
        }

        public IList<IList<int>> levelOrder(TreeNode root)
        {
            List<IList<int>> res = new List<IList<int>>();
            levelHelper(res, root, 0);
            return res;
        }

        public void levelHelper(List<IList<int>> list, TreeNode root, int level)
        {
            //边界条件判断
            if (root == null)
                return;
            //level表示的是层数，如果level >= list.size()，说明到下一层了，所以
            //要先把下一层的list初始化，防止下面add的时候出现空指针异常
            if (level >= list.Count)
            {
                list.Add(new List<int>());
            }
            //level表示的是第几层，这里访问到第几层，我们就把数据加入到第几层
            list[level].Add(root.val);
            //当前节点访问完之后，再使用递归的方式分别访问当前节点的左右子节点
            levelHelper(list, root.left, level + 1);
            levelHelper(list, root.right, level + 1);
        }
    }
}
